package com.giteelou.simple;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 简单的语法分析器。
 * 它能够分析简单的表达式、变量声明和初始化语句、赋值语句。
 * 它支持的语法规则为：
 * <p>
 * program -> intDeclare | expressionStatement | assignmentStatement
 * intDeclare -> 'int' Id ( = additive)? ';'
 * expressionStatement -> additive ';'
 * assignmentStatement -> Id = additive ';'
 * additive -> multiplicative (('+' | '-') multiplicative)*
 * multiplicative -> primary (('*' | '/') primary)*
 * primary -> IntLiteral | Id | (additive)
 */
public class SimpleParser {

    public static void main(String[] args) {
        String script;
        ASTNode node;
        SimpleParser parser = new SimpleParser();
        try {
            script = "int age = 45 + 2; age = 20; age + 10 * 2;";
            System.out.println("解析：" + script);
            node = parser.parse(script);
            parser.dumpAST(node, "|-");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        System.out.println("-------------");

        //测试异常语法
        try {
            script = "2 + 3 + ;";
            System.out.println("解析：" + script);
            node = parser.parse(script);
            parser.dumpAST(node, "|-");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        System.out.println("-------------");

        //测试异常语法
        try {
            script = "2 + 3 * ;";
            System.out.println("解析：" + script);
            node = parser.parse(script);
            parser.dumpAST(node, "|-");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        System.out.println("-------------");

        try {
            script = "int a= 23 * 1 -2;int b = 3 *15 + 17*(2+3/(a + 1))+ 1/ 4* 3 - 8;";
            System.out.println("解析：" + script);
            node = parser.parse(script);
            parser.dumpAST(node, "|-");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        System.out.println("-------------");

    }

    /**
     * 解析 script
     *
     * @param script script
     * @return ASTNode
     * @throws Exception 语法错误
     */
    public ASTNode parse(String script) throws Exception {
        SimpleLexer lexer = new SimpleLexer();
        List<Token> tokenList = lexer.analyze(script);
        Queue<Token> tokens = new LinkedList<>(tokenList);

        SimpleASTNode node = new SimpleASTNode(ASTNodeType.Program, "pwc");
        while (!tokens.isEmpty()) {
            SimpleASTNode child = intDeclare(tokens);
            if (child == null) {
                child = assignmentStatement(tokens);
            }
            if (child == null) {
                child = expressionStatement(tokens);
            }
            if (child == null) {
                throw new Exception("unknown statement");
            }
            node.addChild(child);
        }

        return node;
    }

    /**
     * 打印抽象语法树
     *
     * @param node   node
     * @param indent 缩进
     */
    public void dumpAST(ASTNode node, String indent) {
        System.out.println(indent + node.getType() + " " + node.getText());
        for (ASTNode child : node.getChildren()) {
            dumpAST(child, "| " + indent);
        }
    }

    /**
     * 解析赋值语句
     * assignmentStatement -> Id = additive ';'
     *
     * @param tokens token queue
     * @return ASTNode
     * @throws Exception 语法错误
     */
    private SimpleASTNode assignmentStatement(Queue<Token> tokens) throws Exception {
        if (tokens == null) {
            return null;
        }
        SimpleASTNode node = null;
        Token token = tokens.peek();
        Token rewrite = token;
        if (token != null && token.getType() == TokenType.Identifier) {
            node = new SimpleASTNode(ASTNodeType.AssignmentStmt, token.getText());
            tokens.poll(); // 消费掉 标识符
            token = tokens.peek();
            if (token != null && token.getType() == TokenType.Assignment) {
                tokens.poll(); // 消费掉 赋值符号
                SimpleASTNode additiveNode = additive(tokens);
                if (additiveNode == null) {
                    throw new Exception("invalid assignment statement, expecting an expression");
                }
                node.addChild(additiveNode);
                token = tokens.peek();
                if (token != null && token.getType() == TokenType.Semicolon) {
                    tokens.poll(); // 消费掉 分号
                } else {
                    throw new Exception("invalid statement, missing semicolon");
                }
            } else {
                LinkedList<Token> linkedList = (LinkedList<Token>) tokens;
                linkedList.addFirst(rewrite); // 回溯，吐出之前消化掉的标识符
                node = null;
            }

            if (token != null && (token.getType() == TokenType.Plus
                    || token.getType() == TokenType.Minus
                    || token.getType() == TokenType.Star
                    || token.getType() == TokenType.Slash)) {
                node = expressionStatement(tokens);
            }
        }
        return node;
    }

    /**
     * 解析表达式
     * expressionStatement -> additive ';'
     *
     * @param tokens token queue
     * @return ASTNode
     * @throws Exception 语法错误
     */
    private SimpleASTNode expressionStatement(Queue<Token> tokens) throws Exception {
        if (tokens == null) {
            return null;
        }
        SimpleASTNode node = additive(tokens);
        if (node != null) {
            Token token = tokens.peek();
            if (token != null && token.getType() == TokenType.Semicolon) {
                tokens.poll(); // 消费掉 分号
            } else {
                throw new Exception("invalid statement, missing semicolon");
            }
        }
        return node;
    }

    /**
     * int变量声明语法解析
     *
     * @param tokens token queue
     * @return ASTNode
     * @throws Exception 语法错误
     */
    private SimpleASTNode intDeclare(Queue<Token> tokens) throws Exception {
        if (tokens == null) {
            return null;
        }
        SimpleASTNode node = null;
        Token token = tokens.peek();
        if (token != null && token.getType() == TokenType.Int) {
            tokens.poll(); // 消费掉int
            token = tokens.peek();
            if (token != null && token.getType() == TokenType.Identifier) {
                tokens.poll(); // 消费掉标识符 （变量名称）
                node = new SimpleASTNode(ASTNodeType.IntDeclaration, token.getText());
                token = tokens.peek();
                if (token != null && token.getType() == TokenType.Assignment) {
                    tokens.poll(); // 消费掉 赋值符号
                    SimpleASTNode child = additive(tokens); // 解析 加法表达式
                    if (child == null) {
                        throw new Exception("invalid variable initialization, expecting an expression");
                    }
                    node.addChild(child);
                }
            } else {
                throw new Exception("invalid int declare, variable name expected");
            }

            token = tokens.peek();
            if (token != null && token.getType() == TokenType.Semicolon) {
                tokens.poll(); // 消费掉 分号
            } else {
                throw new Exception("invalid statement, missing semicolon");
            }
        }
        return node;
    }

    /**
     * 解析加法表达式
     * additive -> multiplicative (('+' | '-') multiplicative)*
     *
     * @param tokens token queue
     * @return ASTNode
     * @throws Exception 语法错误
     */
    private SimpleASTNode additive(Queue<Token> tokens) throws Exception {
        SimpleASTNode child1 = multiplicative(tokens);
        if (child1 != null) {
            while (true) {
                Token token = tokens.peek();
                if (token != null && (token.getType() == TokenType.Plus || token.getType() == TokenType.Minus)) {
                    tokens.poll();
                    SimpleASTNode parent = new SimpleASTNode(ASTNodeType.AdditiveExp, token.getText());
                    SimpleASTNode child2 = multiplicative(tokens);
                    if (child2 != null) {
                        parent.addChild(child1);
                        parent.addChild(child2);
                        child1 = parent;
                    } else {
                        throw new Exception("invalid additive expression, missing right part");
                    }
                } else {
                    break;
                }
            }
        }
        return child1;
    }

    /**
     * 解析乘法表达式
     * multiplicative -> primary (('*' | '/') primary)*
     *
     * @param tokens token queue
     * @return ASTNode
     * @throws Exception 语法错误
     */
    private SimpleASTNode multiplicative(Queue<Token> tokens) throws Exception {
        SimpleASTNode child1 = primary(tokens);
        if (child1 != null) {
            while (true) {
                Token token = tokens.peek();
                if (token != null && (token.getType() == TokenType.Star || token.getType() == TokenType.Slash)) {
                    tokens.poll();
                    SimpleASTNode parent = new SimpleASTNode(ASTNodeType.MultiplicativeExp, token.getText());
                    SimpleASTNode child2 = primary(tokens);
                    if (child2 != null) {
                        parent.addChild(child1);
                        parent.addChild(child2);
                        child1 = parent;
                    } else {
                        throw new Exception("invalid multiplicative expression, missing right part");
                    }
                } else {
                    break;
                }
            }
        }
        return child1;
    }

    /**
     * 解析基础表达式
     * primary -> IntLiteral | Id | (additive)
     *
     * @param tokens token queue
     * @return ASTNode
     * @throws Exception 语法错误
     */
    private SimpleASTNode primary(Queue<Token> tokens) throws Exception {
        SimpleASTNode node = null;
        Token token = tokens.peek();
        if (token != null) {
            if (token.getType() == TokenType.IntLiteral) {
                tokens.poll(); // 消费掉 数字字面量
                node = new SimpleASTNode(ASTNodeType.IntLiteral, token.getText());
            } else if (token.getType() == TokenType.Identifier) {
                tokens.poll(); // 消费掉 标识符
                node = new SimpleASTNode(ASTNodeType.Identifier, token.getText());
            } else if (token.getType() == TokenType.LeftParenthesis) {
                tokens.poll(); // 消费掉 左括弧
                node = additive(tokens); // 再解析加法表达式
                if (node == null) {
                    throw new Exception("expecting an additive expression inside parenthesis");
                }
                token = tokens.peek();
                if (token != null && token.getType() == TokenType.RightParenthesis) {
                    tokens.poll(); // 消费掉 右括弧
                } else {
                    throw new Exception("expecting right parenthesis");
                }
            }
        }
        return node;
    }

    /**
     * 简单的ASTNode实现。
     */
    private static class SimpleASTNode implements ASTNode {
        private final ASTNodeType type;
        private final String text;
        private ASTNode parent;
        private final List<ASTNode> children;

        public SimpleASTNode(ASTNodeType type, String text) {
            this.type = type;
            this.text = text;
            children = new ArrayList<>();
        }

        public void addChild(SimpleASTNode node) {
            children.add(node);
            node.parent = this;
        }

        @Override
        public ASTNodeType getType() {
            return type;
        }

        @Override
        public String getText() {
            return text;
        }

        @Override
        public ASTNode getParent() {
            return parent;
        }

        @Override
        public List<ASTNode> getChildren() {
            return children;
        }
    }
}
